#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    char data;
    struct BiTNode *LChild, *RChild;
} BiTNode, *BiTree;

void createBitree(BiTree *Bt) {
    char ch;
    ch = getchar();

    if (ch =='#') {
        *Bt = NULL; 
    } else {
        *Bt = (BiTree)malloc(sizeof(BiTNode));
        if (*Bt == NULL) {
            printf("内存分配失败");
            exit(1);
        }
        (*Bt)->data = ch; 
        createBitree(&((*Bt)->LChild)); 
        createBitree(&((*Bt)->RChild));
    }
}

void inorderTraversal(BiTree root) {
    if (root != NULL) {
        inorderTraversal(root->LChild);
        printf("%c ", root->data);
        inorderTraversal(root->RChild);
    }
}

void freeBitree(BiTree root) {
    if (root != NULL) {
        freeBitree(root->LChild);
        freeBitree(root->RChild);
        free(root);
    }
}

int main() {
    BiTree root = NULL;
    printf("请用层序遍历的方式输入二叉树（#表示空节点):\n");
    createBitree(&root); 

    printf("二叉树的中序遍历:\n");
    inorderTraversal(root); 
    printf("\n");

    freeBitree(root); 
    return 0;
}